package com.cherrish.demo.algorithm;

import java.util.Collections;

/**
 * @author cherrish
 * @time 2019-01-17 11:09
 * @name AlgorithmImpl
 * @desc:
 */
public class AlgorithmImpl extends AbstractAlgorithm {
    public static void main(String[] args) {
        Collections.binarySearch(Collections.EMPTY_LIST, 0);
        int[] arr = new int[]{1,3,4,5,7,8,9,11,12,13,20,25,26,28};
        System.out.println(arr.length);
        int index = binarySearch(arr, 13);
        System.out.println(index);
        System.out.println(arr[index]);

        int[] arr1 = {2,1,4,4,7,8,8,3,11, 101, 202,303, 808,666,711,333,222,111,555,888,999 ,99,100,10,33,22,44,66,55,77,88};
//        bubbleSort(arr1, arr1.length);
//        selectSort(arr1, arr1.length);
//        insertSort(arr1, arr1.length);
        hellSort(arr1, arr1.length);
        for(int i = 0; i < arr1.length; i++){
            System.out.print(arr1[i] + " ");
        }
        System.out.println();
    }

    static private void hellSort(int[] arr, int len){
        int h = 1;
        while (h < len / 3) {
            h = 3 * h + 1;
        }
        System.out.println("arr.length = "+ len +", h = " + h);
        for (; h >= 1; h /= 3) {
            System.out.println("h = " + h);
            for (int i = 0; i < len - h; i += h) {
                System.out.print("i = " + i + "[ ");
                for (int j = i + h; j > 0; j -= h) {
                    System.out.print(j + " ");
                    if (arr[j] < arr[j - h]) {
                        swap(arr, j, j - h);
//                        int temp = arr[j];
//                        arr[j] = arr[j - h];
//                        arr[j - h] = temp;
                    }
                }
                System.out.println(" ]");
            }
        }
    }

    static private void insertSort(int[] arr, int len){
        for(int i = 1; i < len; i++){
            for(int j = 0; j < len; j++){
                if(arr[i] < arr[j]){
                    swap(arr, i , j);
                }
            }
        }
    }

    static private void selectSort(int[] arr, int len){
        for(int i = 0; i < len; i++){
            int min = i;
            for(int j = i + 1; j < len; j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            if(i != min){
                swap(arr, i, min);
            }
        }
    }

    static private void bubbleSort(int[] arr, int len){
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len - i -1; j++){
                if(arr[j] > arr[j + 1]){
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    /**
     *
     * 算法名称：二分排序(折半插入排序)
     * 算法描述：当直接插入排序进行到某一趟时，前i-1个记录已有序，此时
     *        不用直接插入排序，而改为二分折半查找，找到后再插入
     * 算法改进：将比较次数减少至O(nlogn)，但移动次数仍为O(n^2)
     *
     * 复杂度分析：
     * 1.平均时间复杂度：O(n^2)
     * 2.空间复杂度：O(1)(临时数据交换空间)
     */
    private static void binarySort(int[] arr){
        int low, mid, high, temp;
        for(int i = 0; i < arr.length; i++){
            temp = arr[i];
            low = 0;
            high = i - 1;
            while (low <= high){
                mid = (low + high) / 2;
                if(arr[mid] > temp){
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }
            }
            for(int j = i - 1; j > high; j--){
                arr[j+1] = arr[j];
            }
            arr[high+1] = temp;
        }
    }

    private static int binarySearch(int[] arr, int val){
        int low = 0;
        int high = arr.length - 1;
        while (low <= high){
            int mid = (low + high) >>> 1;
            int midVal = arr[mid];
            if(val < midVal){
                high = mid - 1;
            }else if(val > midVal){
                low = mid + 1;
            }else {
                return mid;
            }
        }
        return -(low + 1);
    }
}
